package tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class buildTree {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] preorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

//        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
        return findNode(inorder, 0, inorder.length, preorder, 0, preorder.length);
    }

//    /**
//     * 中后序遍历构建二叉树
//     * @param inorder 中序遍历
//     * @param inBegin
//     * @param inEnd
//     * @param postorder 后序遍历
//     * @param postBegin
//     * @param postEnd
//     * @return
//     */
//    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd){
//        if (inBegin >= inEnd || postBegin >= postEnd){
//            return null;
//        }
//        int rootIndex = map.get(postorder[postEnd - 1]);
//        TreeNode root = new TreeNode(inorder[rootIndex]);
//        int lenOfLeft = rootIndex - inBegin;
//        root.left = findNode(inorder, inBegin, rootIndex,
//                postorder, postBegin, postBegin + lenOfLeft);
//        root.right = findNode(inorder, rootIndex + 1, inEnd,
//                postorder, postBegin + lenOfLeft, postEnd - 1);
//
//        return root;
//    }
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int pretEnd){
        if (inBegin >= inEnd || preBegin >= pretEnd){
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenOfLeft = rootIndex - inBegin;
        root.left = findNode(inorder, inBegin, rootIndex,
                preorder, preBegin + 1, preBegin + lenOfLeft + 1);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                preorder, preBegin + lenOfLeft + 1, pretEnd);
        return root;
    }
}

